package gsolver;

import org.apache.commons.math.genetics.Population;
import org.apache.commons.math.genetics.Chromosome;
import org.apache.commons.math.genetics.ListPopulation;

import gsolver.GChromosome;
import gsolver.GeneticSolver;

import java.util.List;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.AbstractMap;
import java.util.Iterator;
import java.util.Comparator;

/**
 * Population de l'algorithme génétique, pour une sélection
 * avec roulette et élitisme à mémoire.
 */
public class GPopulation implements Population {
    /* File de priorité contenant la population, avec le meilleur chromosome en tête */
    private PriorityQueue<Chromosome> chromosomes;
    /* Tableau de paire associant à chaque probabilité sommée le chromosome correspondant */
    private PaireFitnessCumuleeChromosome[] sommeFitness;
    /* Nombre de générations restantes avant rajout à la population des meilleurs
       individus. */
    private int delaiElitisme;
    /* File de priorité contenant l'élite de la population, avec le moins bon chromosome
       en tête. */
    private PriorityQueue<Chromosome> elite;

    public class ComparatorFitness implements Comparator<Chromosome> {
	public ComparatorFitness() {
	    return;
	}

	public int compare(Chromosome c1, Chromosome c2) {
	    return (int)Math.round(c1.fitness() - c2.fitness());
	}
    }

    public class ComparatorFitnessInverse implements Comparator<Chromosome> {
	public ComparatorFitnessInverse() {
	    return;
	}

	public int compare(Chromosome c1, Chromosome c2) {
	    return (int)Math.round(c2.fitness() - c1.fitness());
	}
    }

    /**
     * Construit une population avec un maximum de populationLimit individus,
     * delaiElitisme generations avant ajout de l'elite a la population, et
     * son élite elite d'un maximum de eliteLimite individus.
     */
    public GPopulation(PriorityQueue<Chromosome> nouveauxChromosomes, 
		       int delaiElitisme, PriorityQueue<Chromosome> nouvelleElite) {
	this.chromosomes = nouveauxChromosomes;
	this.elite = nouvelleElite;
	this.delaiElitisme = delaiElitisme;
	this.sommeFitness = null;
    }
    
    public void addChromosome(Chromosome chromosome) {
	chromosomes.offer(chromosome);
    }

    public Chromosome getFittestChromosome() {
	return chromosomes.peek();
    }

    public GChromosome getFittestGChromosome() {
	return (GChromosome)(chromosomes.peek());
    }

    public int getPopulationLimit() {
	return GeneticSolver.populationLimit;
    }

    public int getPopulationSize() {
	return chromosomes.size();
    }

    public Iterator<Chromosome> iterator() {
	return chromosomes.iterator();
    }

    public static class PaireFitnessCumuleeChromosome 
	implements Comparable<PaireFitnessCumuleeChromosome> {
	public final double fitnessCumulee;
	public final Chromosome chromosome;

	public PaireFitnessCumuleeChromosome(double fitnessCumulee, Chromosome chromosome) {
	    this.fitnessCumulee = fitnessCumulee;
	    this.chromosome = chromosome;
	}

	public int compareTo(PaireFitnessCumuleeChromosome p2) {
	    return (int)Math.round(this.fitnessCumulee - p2.fitnessCumulee);
	}
    }

    public PaireFitnessCumuleeChromosome[] getSommeFitness() {
	if (sommeFitness == null) {
	    sommeFitness = new PaireFitnessCumuleeChromosome[chromosomes.size()];
	    double accum = 0;
	    int i = 0;

	    for (Chromosome c : chromosomes) {
		sommeFitness[i] = new PaireFitnessCumuleeChromosome(accum + c.fitness(), c);
		accum = sommeFitness[i].fitnessCumulee;
		i++;
	    }
	}

	return sommeFitness;
    }

    /**
     * Initialise une population à remplir pour la prochaine génération.
     */
    public Population nextGeneration() {
	remplirElite();

	if (delaiElitisme == 0) {
	    PriorityQueue<Chromosome> nouvellePopulation = 
		new PriorityQueue<Chromosome>(GeneticSolver.populationLimit,
					      new ComparatorFitness());
	    nouvellePopulation.retainAll(elite);
	    
	    return new GPopulation(nouvellePopulation, GeneticSolver.delaiElitisme,
				   new PriorityQueue<Chromosome>(GeneticSolver.delaiElitisme,
								 new ComparatorFitnessInverse()));
	} else {
	    return new GPopulation(new PriorityQueue<Chromosome>(GeneticSolver.populationLimit,
								 new ComparatorFitness()),
				   delaiElitisme - 1, elite);
	}
    }

    /**
     * Remplit l'élite avec les meilleurs individus de la population, une fois remplie
     * ajoute a l'élite les individus de la population meilleurs que les moins bons de l'élite.
     */
    public void remplirElite() {
	PriorityQueue<Chromosome> copieChromosomes = new PriorityQueue<Chromosome>(chromosomes);

	while (elite.size() < GeneticSolver.populationLimit) {
	    elite.offer(copieChromosomes.poll());
	}

	if (!copieChromosomes.isEmpty()) {
	    while (elite.peek().fitness() > copieChromosomes.peek().fitness()) {
		elite.offer(copieChromosomes.poll());
	    }
	}
    }
}